package com.Oct_TwentyFive;

import java.util.ArrayDeque;
import java.util.IllegalFormatCodePointException;
import java.util.Queue;

/**
 * 934. 最短的桥
 * 给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。
 *
 * 岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。
 *
 * 你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。
 *
 * 返回必须翻转的 0 的最小数目。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/shortest-bridge
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/10/25 12:56
 */

public class Solution934 {

    public int shortestBridge(int[][] grid) {
        int[][] dir={{-1,0},{1,0},{0,-1},{0,1}};
        int n=grid.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]==1)
                {
                    Queue<int[]> queue=new ArrayDeque<>();
                    dfs(i,j,grid,queue);
                    int cnt=0;
                    while (!queue.isEmpty())
                    {
                        int sz=queue.size();
                        for (int k = 0; k < sz; k++) {
                            int[] tmp=queue.poll();
                            //assert tmp != null;
                            int nx=tmp[0],ny=tmp[1];
                            for (int l = 0; l < 4; l++) {
                                int dx=nx+dir[l][0];
                                int dy=ny+dir[l][1];
                                if (dx<0||dx>=n||dy<0||dy>=n) continue;
                                if (grid[dx][dy]==0)
                                {
                                    queue.add(new int[]{dx,dy});
                                    grid[dx][dy]=-1;
                                }else if (grid[dx][dy]==1)
                                {
                                    return cnt;
                                }
                            }
                        }
                        cnt++;
                    }
                }
            }
        }
        return 0;
    }

    void dfs(int x, int y, int[][] grid, Queue<int[]> queue){
        if (x<0||x>=grid.length||y<0||y>=grid.length||grid[x][y]!=1)
        {
            return;
        }
        queue.add(new int[]{x,y});
        grid[x][y]=-1;
        dfs(x-1,y,grid,queue);
        dfs(x+1,y,grid,queue);
        dfs(x,y-1,grid,queue);
        dfs(x,y+1,grid,queue);
    }

    public static void main(String[] args) {
        Solution934 solution934=new Solution934();
        System.out.println(solution934.shortestBridge(new int[][]{{1,1,1,1,1},{1,0,0,0,1},{1,0,1,0,1},{1,0,0,0,1},{1,1,1,1,1}}));
    }
}
